//==================================================================
//  Copyright (C) 2006-2007  Davide Pasca
//
//  This library is free software; you can redistribute it and/or
//  modify it under the terms of the GNU Lesser General Public
//  License as published by the Free Software Foundation; either
//  version 2.1 of the License, or (at your option) any later version.
//
//  This library is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
//  Lesser General Public License for more details.
//
//  You should have received a copy of the GNU Lesser General Public
//  License along with this library; if not, write to the Free Software
//  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
//==================================================================
///
///
///
///
///
//==================================================================

#include "stdafx.h"
#include "psys.h"
#include "m5d_mesh.h"
#include "m5d_tvert.h"
#include <algorithm>

//==================================================================
using namespace M5D;

//==================================================================
bool TriList::FindTriangleWithVerts(	int exclude_tri,
										const MeshGeometry *gp,
										int v1, int v2 )
{
	int	*tlistp = &_listp.front();

	for (int i=_listp.size(); i; --i)
	{
		int tr_i = *tlistp++;
		if ( tr_i != exclude_tri )
		{
			const Triangle	*trianglep = &gp->GetTrigs()._list[ tr_i ];
			if ( trianglep->IsValid() )
			{		
				int v1_match_cnt = 0;
				int v2_match_cnt = 0;
				for (int j=0; j < 3; ++j)
				{
					if ( trianglep[0][j] == v1 )	++v1_match_cnt;
					if ( trianglep[0][j] == v2 )	++v2_match_cnt;
				}

				if ( v1_match_cnt + v2_match_cnt == 2 )
					return true;
			}
		}
	}

	return false;
}

//==================================================================
// this routine makes sure that the vertex vidx isn't part of an open edge
// of any triangle
void TriList::MarkOpenEdges( int vidx, const MeshGeometry *gp )
{
	// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
	// not checking if checking one triangle against itself !!!???

	// for all triangles in the vertex vidx
	for (int i=0; i < _listp.size(); ++i)
	{
		int					tri				= _listp[i];
		const Triangle	*triangle_ip	= &gp->GetTrigs()._list[ tri ];
		if ( triangle_ip->IsValid() )
		{
			int	vidx_a;
			int	vidx_b;
			
			PASSERT( triangle_ip[0][0] == vidx || triangle_ip[0][1] == vidx || triangle_ip[0][2] == vidx );
			
			if ( triangle_ip[0][0] == vidx )
			{
				vidx_a = triangle_ip[0][1];
				vidx_b = triangle_ip[0][2];
			}
			else
			if ( triangle_ip[0][1] == vidx )
			{
				vidx_a = triangle_ip[0][0];
				vidx_b = triangle_ip[0][2];
			}
			else
			{
				vidx_a = triangle_ip[0][0];
				vidx_b = triangle_ip[0][1];
			}

			if ( !FindTriangleWithVerts( tri, gp, vidx, vidx_a ) ||
				 !FindTriangleWithVerts( tri, gp, vidx, vidx_b ) )
			{
				_flags |= TriList::FLG_OPEN_EDGE;
				return;
			}
		}
	}
}

//==================================================================
PError tvert_update_vert_count( TriIdx_VertIdx *T, MeshGeometry *gp )
{
	if ( T->len() < gp->GetVerts().GetPosN() )
	{
		int n_add = gp->GetVerts().GetPosN() - T->len();

		PASSERT( 0 );
		// $$$ need to add this back - T->_lists.expand( n_add );
	}

	return POK;
}

//==================================================================
void TriIdx_VertIdx::RemoveMarkedVerts()
{
	int	d = 0;

	for (int i=0; i < _lists.size(); ++i)
	{
		if ( _lists[i]._flags & TriList::FLG_DOREMOVE )
		{
			_lists[i].~TriList();
		}
		else
		{
			if ( i != d )
				_lists[d] = _lists[i];

			++d;
		}
	}
}

//==================================================================
void TriList::RemTri( int tidx )
{
	int is = 0;
	int id = 0;

	int	match_cnt = 0;

	for (; is < _listp.size(); ++is)
	{
		if ( _listp[is] != tidx )
			_listp[id++] = _listp[is];
		else
			++match_cnt;
	}

	PASSERT( match_cnt == 1 );

	_listp.resize( id );
}

//==================================================================
// - needs to somehow mark the verts that are not used anymore
int TriIdx_VertIdx::ReplaceVertex( int good_vidx, int kill_vidx, MeshGeometry *gp )
{
	int	n_killed_trigs = 0;

	PASSERT( good_vidx >= 0 );

	TriList	&good_v_list = _lists[ good_vidx ];
	TriList	&kill_v_list = _lists[ kill_vidx ];

	// save the tri_list for the vertex to kill
	TriList	kill_v_list_tmp( kill_v_list );
		
	// if it's not an open edge then moves the good vert to minimize damage
	if NOT( (good_v_list._flags | kill_v_list._flags) & TriList::FLG_OPEN_EDGE )
	{
		Vector3			&pos1 = gp->GetVerts().GetPosW()[ good_vidx ];
		const Vector3	&pos2 = gp->GetVerts().GetPosR()[ kill_vidx ];

		// collapses in the middle
		//pos1 = (pos1 + pos2) * 0.5f;


		// $$$ doesn't deal with texture and normals !
		// to do that, it may need to work on a higher level vertex like the
		// wedge thing from Hoppe
	}

	const Vector3	*pos_vertsp = gp->GetVerts().GetPosR();

	// for every triangle that shows in the vertex to kill,
	// either replace the vertex or kill the whole triangle
	// if it collapses
	int	nt = kill_v_list_tmp.len();
	for (int i=0; i < nt; ++i)
	{
		int tr_i = kill_v_list_tmp[ i ];

		Triangle	&tri = gp->GetTriangle( tr_i );
		if NOT( tri.IsValid() )
			continue;

		// how many good and to-kill vertices does this triangle have ?
		int good_cnt = 0;
		int kill_cnt = 0;
		for (int j=0; j < 3; ++j)
		{
			if ( tri[j] == good_vidx )	++good_cnt;
			if ( tri[j] == kill_vidx )	++kill_cnt;
		}

		// it must have maximum one count of each, otherwise the triangle has
		// duplicate vertices -> it's degenerated

		// killable vertex must be one
		PASSERT( kill_cnt == 1 );

		// good vertex could be there
		PASSERT( good_cnt == 0 || good_cnt == 1 );

		// if the triangle lists a good vertex and a kill vertex
		if ( good_cnt && kill_cnt )
		{
			// then the good one replaced the bad one and the triangle
			// has collapsed, so we remove it
			_lists[ tri[0] ].RemTri( tr_i );
			_lists[ tri[1] ].RemTri( tr_i );
			_lists[ tri[2] ].RemTri( tr_i );

			tri.Invalidate();
			++n_killed_trigs;
		}
		else
		{
			kill_v_list.RemTri( tr_i );	// remove triangle from the bad vertex
			good_v_list.AddTri( tr_i );	// add triangle to the good vertex

			// replace the indices into the triangle
			if ( tri[0] == kill_vidx )	tri[0] = good_vidx;
			if ( tri[1] == kill_vidx )	tri[1] = good_vidx;
			if ( tri[2] == kill_vidx )	tri[2] = good_vidx;
		}

		// recalc the triangle plane
		tri.CalcPlane( pos_vertsp );
	}

	// recalc the normals of the triangles that have the good vertex because
	// that has changed too
	nt = good_v_list.len();
	for (int i=0; i < nt; ++i)
	{
		int tr_i = good_v_list[ i ];

		Triangle	&tri = gp->GetTriangle( tr_i );
		if NOT( tri.IsValid() )
			continue;

		// do NOT recalc the triangle plane/normal...
		// because we actually care for the original normal,
		// not the one we messed up in the reduction process !!
		//tri.CalcPlane( pos_vertsp );
	}

	return n_killed_trigs;
}

//==================================================================
void TriList::AddTri( int tidx )
{
	_listp.push_back( tidx );
}

//==================================================================
void TriList::PreallocBegin()
{
	PASSERT( _pre_cnt == 0 );
	_pre_cnt = 0;
}

//==================================================================
void TriList::PreallocAdd()
{
	++_pre_cnt;
}

//==================================================================
void TriList::PreallocEnd()
{
	_listp.reserve( _pre_cnt );
	_pre_cnt = 0;
}

//==================================================================
void TriIdx_VertIdx::preallocTrilists( const MeshGeometry *gp )
{
	int		nv = gp->GetVerts().GetPosN();
	int		nt = gp->GetTrigs()._list.size();

	const Triangle	*trip;

	trip = &gp->GetTrigs()._list.front();

	// paranoia check
#ifdef _DEBUG
	for (int i=0; i < nt; ++i, ++trip)
	{
		int	v0 = trip->pos[0];
		int	v1 = trip->pos[1];
		int	v2 = trip->pos[2];

		PASSERT( v0 >= 0 && v0 < nv &&
				 v1 >= 0 && v1 < nv &&
				 v2 >= 0 && v2 < nv );
	}
#endif

	for (int i=0; i < nv; ++i)
		_lists[i].PreallocBegin();

	trip = &gp->GetTrigs()._list.front();
	for (int i=0; i < nt; ++i, ++trip)
	{
		_lists[ trip->pos[0] ].PreallocAdd();
		_lists[ trip->pos[1] ].PreallocAdd();
		_lists[ trip->pos[2] ].PreallocAdd();
	}

	for (int i=0; i < nv; ++i)
		_lists[i].PreallocEnd();
}

//==================================================================
void TriIdx_VertIdx::createTrilists( const MeshGeometry *gp )
{
	preallocTrilists( gp );

	int		nt = gp->GetTrigs()._list.size();

	const Triangle	*trip = &gp->GetTrigs()._list.front();

	for (int i=0; i < nt; ++i, ++trip)
	{
		_lists[ trip->pos[0] ].AddTri( i );
		_lists[ trip->pos[1] ].AddTri( i );
		_lists[ trip->pos[2] ].AddTri( i );
	}
}

//==================================================================
struct Edge
{
	int	_v[2];
};

//==================================================================
// Descending date sorting function
struct EdgeAscendSort
{
     PFORCEINLINE bool operator()(const Edge &a, const Edge &b) const
     {
		int diff = a._v[0] - b._v[0];
		
		if ( diff == 0 )
			return a._v[1] < b._v[1];
		else
			return diff < 0;
     }
};

//==================================================================
TriIdx_VertIdx::TriIdx_VertIdx( const MeshGeometry *gp )
{
	int nv = gp->GetVerts().GetPosN();

	_lists.resize( nv );
	createTrilists( gp );

	for (int i=0; i < nv; ++i)
		_lists[i].MarkOpenEdges( i, gp );
}